In the latter half of the twentieth century, there began a phenomenon known as the information revolution. While the information revolution is a historical development broader in scope than any one event or machine, no single device has come to represent the information revolution more than the digital electronic computer. The development of computer systems has surely been a revolution. Each year, computer systems grow faster, store more data, and provide more applications to their users.
At the heart of a computer system is one or more central processing units (CPUs), also called processors, which execute instructions stored in the computer's memory. From the standpoint of the computer's hardware, most systems operate in fundamentally the same manner. Processors are capable of performing a defined set of very simple operations, such as arithmetic, logical comparisons, and movement of data from one location to another. But each operation is performed very quickly. Computer program code at multiple levels directs the computer to perform massive numbers of these simple operations, enabling the computer to perform complex tasks. Although the defined set of simple operations is limited, the possible sequences and combinations of such operations which can be specified in the program code are virtually limitless.
In the very early history of the digital computer, computer programs which instructed the computer to perform some task were written in a form directly executable by the computer's processor. Such programs were very difficult for a human to write, understand and maintain, even when performing relatively simple tasks. As the number and complexity of such programs grew, this method became clearly unworkable. To make computer programs easier to develop, a large and varied set of high-level languages was developed for supporting the creation of computer program code.
High-level languages vary in their characteristics, but all such languages are intended to make it easier for a human to write a program to perform some task. Typically, high-level languages represent operations, fixed values, variables, and other constructs in a manner readily understandable to the human programmer rather than the computer. Such programs are not directly executable by the computer's processor. In order to run on the computer, the programs must first be transformed from a human-readable form (source code) to something executable by the processor of a computer, i.e. to a sequence of instructions directly readable and executable by the processor.
An instruction which is directly readable and executable by the processor (a processor-executable instruction) is a sequence of binary bits in a pre-defined format, each bit position being specific to logic within the processor which reads and decodes it. Combinations of bit values specify an operation or operations to be performed, source or destination of data, branch conditions or destinations, and so forth. The bit sequence formatting and the meaning of the bit combinations defines the “instruction set” of the processor. While the limited set of simple operations performed by any processor is similar to that of another, the instruction set of each processor (i.e., the pre-defined format and meaning of the processor's executable instruction binary bit sequence) is not.
In general, source code is universal and understandable by anyone trained to use the applicable language, while executable code is specific to a particular computer system environment, and can only execute on that computer system or one similarly configured. In particular, the executable code is specific to the processor's instruction set, although it may be specific to other parameters of the computer system as well.
Various techniques exist for transforming the source code in a high-level language to processor-executable instructions in the processor's instruction set. Source code can be “interpreted”, meaning that a special program (an “interpreter”) takes each source code statement in sequence, and executes a small procedure (i.e., series of instructions in the processor-executable instruction set) corresponding to each source code instruction. Interpreting is useful for some purposes, but it is generally rather inefficient.
Traditionally, for greater execution efficiency, individual portions (modules) of source code are compiled to form modules of processor-executable instructions, which may be linked together to form larger programs (although some programs contain only a single compiled module). These programs are saved in digital media storage in executable form, and may be distributed in that form to other computer systems, or remain on the system in which they were first compiled. In this form they are later executed, usually many times. Compilation is itself a task performed by a special computer program (a compiler), and can take significant time. Often, compilation involves certain optimizations to the executable code which require analysis of the various instruction sequences within the program. Unlike interpreted code, the resultant processor-executable instructions in a compiled module do not necessarily correspond to particular source instructions, and do not necessarily follow the same sequence, although they must produce the same logical output. Since it is expected that such programs will be executed many times, the burden of compilation is spread over many executions. This traditional form of compilation is sometimes referred to as “static compilation”.
In recent years, there has been increasing interest in “just-in-time” dynamic compilation or optimization. Like static compilation, “just-in-time” or dynamic compilation/optimization involves the generation of optimized processor-executable instructions. But unlike static compilation, the program's processor-executable instructions are generated during or as part of execution of the program of which the processor-executable instructions are a part (the “target program”). This effectively means that just-in-time or dynamic compilation/optimization is intended to be performed many times, for example, each time the program is executed, or for each user process which executes the program.
Obviously, when compared with traditional static compilation, dynamic compilation/optimization suffers from the drawback that it is performed again each time the program is executed or for each new user process. However, there are various advantages to just-in-time or dynamic compilation/optimization that make it attractive in many circumstances. For example, dynamically compiled code is generated on the system that will execute it, and can be generated from a universal, intermediate level code form (between a high-level source language and a processor-executable form), which facilitates portability of the program. Such an approach is frequently used in the well-known JAVA™ virtual machine environment. Furthermore, additional knowledge available to the system at execution time, such as the exact system configuration, the code modules being used, and the actual pattern of code execution, make it possible to generate more efficient compiled code than can typically be generated using a static compiler. Such additional knowledge is particularly effective in the case of actual code usage patterns, which allow dynamic compilation/optimization to focus on optimizing specific portions of the code.
One form of dynamic compilation is the generation of processor-executable instructions at execution time from previously compiled executable code, generally without use of the original source code. This is known as dynamic binary optimization. Dynamic binary optimization is commonly used to emulate a computer system having a different, often older, instruction set architecture. I.e., an executable computer program which was previously compiled to contain processor-executable instructions in an older instruction set architecture can be recompiled from the previously compiled executable code to generate processor-executable instructions in the instruction set of the current processor.
Although dynamic binary optimization is commonly used to support emulation, it has the potential for improving execution efficiency even where the originally compiled executable code is compiled to the same instruction set architecture as that of the current processor. In other words, even though the previously compiled version of the program is fully capable of execution on the current processor without further compilation, optimization or translation, the execution efficiencies which are possible through dynamic binary optimization may in some circumstances justify the additional overhead of dynamically re-compiling the already compiled code. In some cases, these execution efficiencies may be magnified if the instruction set architecture has been enhanced with new features not utilized by the original statically compiled code (which may be quite old). Typically, only selective portions of the previously compiled code will be re-compiled dynamically, because one of the advantages of dynamic compilation is that it can identify “hot spots” (frequently executed code portions) and focus optimization activity on these hot spots.
One difficulty with dynamic binary optimization of a program using the same instruction set architecture arises because the compiler is generally free to use all available registers in the applicable instruction set architecture for program optimizations. Therefore the target program, when executed in its originally compiled form, often uses all the available registers. Dynamic binary optimization is performed by another program executing on the same computer, called a “virtual machine”. The virtual machine must use these same registers, so the register contents are saved to storage and restored from storage when switching execution contexts between the virtual machine and the target program. In order to save the registers in most computer architectures, at least one register must be available to hold address information for the area in memory where the registers will be saved (the “context save area”). If the target program is compiled to use all available registers, there is no guarantee that a register for holding address information for the context save area will be available.
Although it has been proposed to solve this problem by dynamically locating an unused register, and failing to find one, temporarily storing (“spilling”) the contents of one or more actively used registers to memory, this solution raises various issues of strict register state compatibility and data integrity/security. A need exists, not necessarily recognized, for a better mechanism to support dynamic binary optimization, and particularly to support dynamic binary optimization using the same instruction set architecture as the target program.